문제 소개

문제 링크 : https://boj.kr/4112

Tier : Platinum I

Tag : DP, Bitmasking, Bitfield DP

2x2 블록, 회전 가능한 ㄱ자 블록을 이용하여 N * M 크기의 칸을 모두 채우는 방법의 수를 구하는 문제입니다.

풀이

1. 브루트 포스 풀이를 먼저 생각해보기

먼저 브루트 포스로 푸는 방법을 생각해봅시다.

문제에 따르면, N개의 행과 M개의 열로 구성된 칸이 존재합니다.

1행 1열부터 블럭을 놓은 뒤 그 다음 빈 칸을 찾아 블럭을 놓는 식으로 진행되다가, 마지막에 블럭을 빈 칸 없이 모두 채울 수 있으면 하나의 방법으로 간주할 수 있습니다.

즉, 특정 위치에 특정 블록을 놓으면서 생기는 다양한 분기점에 대해 모두 탐색하는 방식으로 구할 수 있습니다.

그러나, 이러한 방식은 (백트래킹과 같은 최적화를 거쳐도) N과 M이 커질수록 판단해야 하는 방법의 수가 기하급수적으로 증가합니다. 따라서, 다른 방법을 고안해야 합니다.

2. DP를 통해 최적화하기

DP는 브루트 포스와 연관이 깊습니다. 모든 경우를 탐색하여 최적의 해를 구하는 방법은 브루트 포스와 DP 모두 해당되기 때문입니다.

대신, DP는 탐색 과정을 거치면서 재활용할 수 있는 부분은 최대한 재활용하여 연산 횟수를 최소화하는데요, 이를 메모이제이션 (Memoization)이라고 합니다.

이 문제 또한 DP로 연산 횟수를 최소화할 수 있습니다. 어떻게 최적화를 할 수 있을까요?

특정 문제를 DP로 접근하기 위해서는, 임의의 위치에 대해 점화식을 세울 수 있어야 합니다.

3. 점화식을 비롯한 일반적인 규칙 찾기

브루트 포스로 접근할 때를 떠올려봅시다. 특정 위치에 특정 블록을 놓는 경우,

이전에 훑은 칸은 생각하지 않고 그 다음 칸들에 대해 방법의 수를 따지게 될 것입니다.

이때, dp[n][m][?] = (특정 위치에서 특정 블록을 놓을 경우 생기는 방법의 수)로 점화식을 나타낼 수 있을 것입니다.

n과 m은 특정 위치를 나타냅니다.

여기서 ?는 무엇을 나타내야 할까요?

특정 블록을 놓을 때, 블럭은 (빈 칸을 포함하여) 항상 2x2칸을 차지하므로 그 아래 행에'도' 영향을 끼치게 됩니다.

그러나, 특정 위치를 기준으로 바로 아래 행에'만' 영향을 끼치게 되므로 k의 범위를 (현재 위치) ~ (영향이 끼치는 위치)로 좁힐 수 있습니다.

즉, 현재 위치를 0번째라 하면 어떤 블록을 놓아도 M + 1번째 위치까지만 영향을 끼칠 수밖에 없습니다.

따라서, Bitmasking을 활용하여 해당 범위에 존재할 수 있는 블럭의 모든 패턴를 ?로 정하면 됩니다.

4. Top-Down Bitfield DP로 구하기

위의 과정을 통해, 점화식은

dp[n][m][k] = (특정 위치에서 특정 블록을 놓을 경우 생기는 방법의 수) 로 나타낼 수 있습니다.

(n, m은 특정 위치, k는 해당 범위에 존재할 수 있는 블럭의 패턴)

k는 2 ^ (M + 2) 이므로, 시간 복잡도는 O(NM2^(M + 2)) 가 됩니다.

아래의 코드를 통해 점화식에 대한 풀이 과정을 확인하세요.

코드

⚠️ Python 언어 특성상 느리기 때문에, 이 코드로 제출할 경우 시간 초과가 발생합니다. 따라서, 미리 모든 결과를 뽑아놓고 인덱싱하는 방식으로 풀어야 합니다.

1
import sys
2
input = lambda: sys.stdin.readline().rstrip()
3
MOD = int(1e6)
4

5
def solve(N, M):
6
  memo = [[-1] * (1 << (M + 2)) for _ in range(N * M)]
7

8
  def find(idx, bit):
9
    row, col = idx // M, idx % M
10

11
    if memo[idx][bit] >= 0:
12
      return memo[idx][bit]
13

14
    # 마지막 행까지 오면, 더 이상 블록을 채울 수 없다.
15
    if row == N - 1:
16
      memo[idx][bit] = int(bit == (1 << (M - col)) - 1)
17
      return memo[idx][bit]
18

19
    result = 0
20

21
    # 현재 블록이 채워진 경우 넘어간다.
22
    if bit & 1:
23
      result = (result + find(idx + 1, bit >> 1)) % MOD
24

25
    # 2x2 Block
26
    if col + 1 < M and bit & (3 | (3 << M)) == 0:
27
      result = (result + find(idx + 2, (bit | (3 << M)) >> 2)) % MOD
28

29
    # left-top
30
    if col + 1 < M and bit & (3 | (1 << M)) == 0:
31
      result = (result + find(idx + 2, (bit | (1 << M)) >> 2)) % MOD
32

33
    # right-top
34
    if col + 1 < M and bit & (3 | (2 << M)) == 0:
35
      result = (result + find(idx + 2, (bit | (2 << M)) >> 2)) % MOD
36

37
    # left-bottom
38
    if col + 1 < M and bit & (1 | (3 << M)) == 0:
39
      result = (result + find(idx + 1, (bit | (3 << M)) >> 1)) % MOD
40

41
    # right-bottom
42
    if col > 0 and bit & (1 | (3 << (M - 1))) == 0:
43
      result = (result + find(idx + 1, (bit | (3 << (M - 1))) >> 1)) % MOD
44

45
    memo[idx][bit] = result
46
    return result
47

48
  return find(0, 0)
49

50
if __name__ == '__main__':
51
  while data := input():
52
    N, M = map(int, data.split())
53

54
    if N == M == 0:
55
      break
56

57
    print(solve(M, N))
58